package person.bing.fbcloud.leetcode;

/**
 * @author: mengfanbing
 * @date: 2020/11/18 13:27
 */
public class Q134 {
    public static void main(String[] args) {
        int[] gas = {1,2,3,4,5};
        int[] cost = {3,4,5,1,2};
        int i = canCompleteCircuit(gas, cost);
        System.out.println(i);
    }

    public static int canCompleteCircuit(int[] gas, int[] cost) {
        int length = gas.length;
        for (int i=0;i<length;i++){
            if (gas[i]>=cost[i]){
                int nextIndex = i+1;
                int div = gas[i] - cost[i];
                while (div >= 0 && nextIndex != i){
                    if (nextIndex == length){
                        nextIndex = 0;
                    }else {
                        div += gas[nextIndex] - cost[nextIndex];
                        nextIndex++;
                    }
                }
                if (nextIndex == i && div>=0){
                    return i;
                }
            }
        }
        return -1;
    }
}
